|
In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph ''G'' is a set of cycles which are subgraphs of ''G'' and contain all vertices of ''G''. If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. In this case the set of the cycles constitutes a spanning subgraph of ''G''. A disjoint cycle cover of an undirected graph (if it exists) can be found in polynomial time by transforming the problem into a problem of finding a perfect matching in a larger graph.〔.〕 〔http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problem 1)〕 If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover. Similar definitions may be introduced for digraphs, in terms of directed cycles. ==Properties and applications== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vertex cycle cover」の詳細全文を読む スポンサード リンク
|